package java_dataLearn;
import java.util.*;

public class Linked {
    public static void main(String[] args) {

    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

//class MyQueue {
//    Stack<Integer> stack1;
//    Stack<Integer> stack2;
//    public MyQueue() {
//        stack1=new Stack<>();
//        stack2=new Stack<>();
//    }
//
//    public void push(int x) {
//        stack1.push(x);
//    }
//
//    public int pop() {
//        if ( empty() ){
//            return -1;
//        }
//        if ( !stack2.isEmpty() ){
//            return stack2.pop();
//        }else{
//            int size=stack1.size();
//            for ( int i=0;i<size;i++ ){
//                stack2.push(stack1.pop());
//            }
//            return stack2.pop();
//        }
//    }
//
//    public int peek() {
//        if ( empty() ){
//            return -1;
//        }
//        if ( !stack2.isEmpty() ){
//            return stack2.peek();
//        }else{
//            int size=stack1.size();
//            for ( int i=0;i<size;i++ ){
//                stack2.push(stack1.pop());
//            }
//            return stack2.peek();
//        }
//    }
//
//    public boolean empty() {
//        return stack1.isEmpty() && stack2.isEmpty();
//    }
//}

//class MyStack {
//
//    Queue<Integer> que1;
//    Queue<Integer> que2;
//
//    public MyStack() {
//        que1=new LinkedList<>();
//        que2=new LinkedList<>();
//    }
//
//    public void push(int x) {
//        if ( !que1.isEmpty() ){
//            que1.offer(x);
//        }else if ( !que2.isEmpty() ){
//            que2.offer(x);
//        }else{
//            que1.offer(x);
//        }
//    }
//
//    public int pop() {
//        if ( empty() ){
//            return -1;
//        }
//        if ( !que1.isEmpty() ){
//            int size=que1.size();
//            for ( int i=0;i<size-1;i++ ){
//                que2.offer(que1.poll());
//            }
//            return que1.poll();
//        }else {
//            int size=que2.size();
//            for ( int i=0;i<size-1;i++ ){
//                que1.offer(que2.poll());
//            }
//            return que2.poll();
//        }
//    }
//
//    public int top() {
//        if ( empty() ){
//            return -1;
//        }
//        if(!que1.isEmpty()) {
//            int size = que1.size();
//            int val = -1;
//            for (int i = 0; i < size; i++) {
//                val = que1.poll();
//                que2.offer(val);
//            }
//            return val;
//        }else {
//            int size = que2.size();
//            int val = -1;
//            for (int i = 0; i < size; i++) {
//                val = que2.poll();
//                que1.offer(val);
//            }
//            return val;
//        }
//    }
//
//    public boolean empty() {
//        return que1.isEmpty() && que2.isEmpty();
//    }
//}

//class Solution {
//    public int evalRPN(String[] tokens) {
//        Stack<String> stack=new Stack<>();
//        for ( int i=0;i<tokens.length;i++ ){
//            if ( tokens[i].equals("+")||tokens[i].equals("-")||tokens[i].equals("*")||tokens[i].equals("/")){
//                String str=tokens[i];
//                int b=Integer.valueOf(stack.pop());
//                int a=Integer.valueOf(stack.pop());
//                int c=0;
//                switch (str){
//                    case "+":
//                        c=a+b;
//                        break;
//                    case "-":
//                        c=a-b;
//                        break;
//                    case "*":
//                        c=a*b;
//                        break;
//                    case "/":
//                        c=a/b;
//                        break;
//                }
//                stack.push(String.valueOf(c));
//            }else{
//                stack.push(tokens[i]);
//            }
//        }
//        return Integer.valueOf(stack.pop());
//    }
//}

//class Solution {
//    public ListNode detectCycle(ListNode head) {
//        if ( head==null || head.next==null ){
//            return null;
//        }
//        ListNode fast=head;
//        ListNode slow=head;
//        while ( fast!=null && fast.next!=null ){
//            fast=fast.next.next;
//            slow=slow.next;
//            if ( fast==slow ){
//                break;
//            }
//        }
//        if ( fast!=slow ){
//            return null;
//        }
//        slow=head;
//        while ( slow!=fast ){
//            slow=slow.next;
//            fast=fast.next;
//        }
//        return fast;
//    }
//}

//class Solution {
//    public boolean hasCycle(ListNode head) {
//        ListNode fast=head;
//        ListNode slow=head;
//        while ( fast!=null && fast.next!=null ){
//            slow=slow.next;
//            fast=fast.next.next;
//            if ( slow==fast ){
//                return true;
//            }
//        }
//        return false;
//    }
//}

//class Solution {
//    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//        if ( headA==null && headB==null ){
//            return null;
//        }
//        int lenA=0;
//        int lenB=0;
//        ListNode nodeA=headA;
//        ListNode nodeB=headB;
//        while ( nodeA!=null ){
//            lenA++;
//            nodeA=nodeA.next;
//        }
//        while ( nodeB!=null ){
//            lenB++;
//            nodeB=nodeB.next;
//        }
//        nodeA=headA;
//        nodeB=headB;
//        int len=lenA-lenB;
//        if ( len<0 ){
//            nodeA=headB;
//            nodeB=headA;
//            len=lenB-lenA;
//        }
//        while ( len!=0 ){
//            nodeA=nodeA.next;
//            len--;
//        }
//        while ( nodeA!=nodeB ){
//            nodeA=nodeA.next;
//            nodeB=nodeB.next;
//        }
//        return nodeA;
//    }
//}

//class Solution {
//    public ListNode middleNode(ListNode head) {
//        ListNode fast=head;
//        ListNode slow=head;
//        while ( fast!=null && fast.next!=null ){
//            fast=fast.next.next;
//            slow=slow.next;
//        }
//        return slow;
//    }
//}

//class Solution {
//    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//        ListNode res=new ListNode();
//        ListNode p=res;
//        while ( list1 != null || list2 != null ){
//            if ( list1 == null ){
//                p.next=list2;
//                p=p.next;
//                list2=list2.next;
//                continue;
//            }
//            if ( list2 == null ){
//                p.next=list1;
//                p=p.next;
//                list1=list1.next;
//                continue;
//            }
//            if ( list1.val <= list2.val ){
//                p.next=list1;
//                p=p.next;
//                list1=list1.next;
//            }else{
//                p.next=list2;
//                p=p.next;
//                list2=list2.next;
//            }
//        }
//        return res.next;
//    }
//}

//class Solution {
//    public ListNode removeElements(ListNode head, int val) {
//        if ( head==null ){
//            return null;
//        }
//        ListNode pre=head;
//        ListNode cur=head.next;
//
//        while ( cur!=null ){
//            if ( cur.val==val ){
//                cur=cur.next;
//                pre.next=cur;
//            }else{
//                pre=cur;
//                cur=cur.next;
//            }
//        }
//        if ( head.val==val ){
//            head=head.next;
//        }
//        return head;
//    }
//}

